
"""
95. 不同的二叉搜索树 II
"""
from typing import List, Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        """
         * 思路：该题和96题思路一样，只需要将辅助函数的返回结果变更下即可，count(low, high)函数返回区间[lwo, high]组成的树的集合，
         *      再根据返回结果，穷举的组合成左右子树
        """
        return self.count(1, n)

    def count(self, low: int, high: int) -> List[Optional[TreeNode]]:
        """
        区间[lwo, high]组成的树的集合
        @param low: 下标
        @param high: 上标标
        @return: 构建的树集合
        """
        res = []
        if low > high:
            res.append(None)
            return res

        # 穷举所有区间内所有数据最为根节点
        for i in  range(low, high + 1):
            # 构建左子树集合
            lefts = self.count(low, i - 1)
            # 构建右子树集合
            rights = self.count(i + 1, high)
            # 穷举所有结果构建树
            for left in lefts:
                for right in rights:
                    root = TreeNode(i)
                    root.left = left
                    root.right = right
                    res.append(root)

        return res
